package org.bear.tree;


import java.util.*;

public class Solution {
    int maxDepth = -1;
    List<TreeNode> valList = new ArrayList<>();

    List<TreeNode> record = new ArrayList<>();


    public void dfs(TreeNode root, int curDepth) {
        if (root!=null){
            if (curDepth==maxDepth){
                valList.add(root);
            } else if (curDepth>maxDepth){
                valList.clear();
                valList.add(root);
                maxDepth = curDepth;
            }
            dfs(root.left,curDepth+1);
            dfs(root.right,curDepth+1);
        }
    }



    public void tailOrder(TreeNode root){
        ArrayList<TreeNode> stack = new ArrayList<>();
        TreeNode p = root;
        TreeNode q = null;
        int count = 0;
        while (p!=null||!stack.isEmpty()){
            while (p!=null){
                stack.add(p);
                p = p.left;
            }
            p = stack.get(stack.size()-1);
            if (p.right==null||p.right==q){
                // visit p
                q = p;
                if (valList.contains(p)){
                    count++;
                    if (record.isEmpty()){
                        record.addAll(stack);
                    }else {
                        for(int j=0;j<record.size();j++){
                            if(record.get(j)!=stack.get(j)){
                                record = record.subList(0,j);
                                break;
                            }
                        }
                    }
                    if (count==valList.size()){
                        return;
                    }
                }
                stack.remove(stack.size()-1);
                p = null;
            }else {
                p = p.right;
            }
        }
    }


    public TreeNode lcaDeepestLeaves2(TreeNode root) {
        dfs(root,0);
        if (valList.size()==1){
            return valList.get(0);
        }else {
            // get lcaDeepestLeaves
            tailOrder(root);
            return record.get(record.size()-1);
        }
    }


    public TreeNode lcaDeepestLeaves(TreeNode root) {
        Object[] objects = dfsDepth(root);
        return (TreeNode)objects[1];
    }


    public Object[] dfsDepth(TreeNode root){
        Object[] objects = new Object[2];
        if(root!=null){
            Object[] left = dfsDepth(root.left);
            Object[] right = dfsDepth(root.right);
            if ((int)left[0]==(int)right[0]){
                objects[0] = (int)left[0] + 1;
                objects[1] = root;
            }else if ((int)left[0]<(int)right[0]){
                objects[0] = (int)right[0] + 1;
                objects[1] = right[1];
            }else {
                objects[0] = (int)left[0] + 1;
                objects[1] = left[1];
            }
        }else {
            objects[0] = 0;
         }
        return objects;
    }









    public static void main(String[] args) {
//        Tree tree = new Tree(new ArrayList<Integer>(Arrays.asList(3,5,1,6,2,0,8,null,null,7,4)));
//        Solution solution = new Solution();
//        TreeNode treeNode = solution.lcaDeepestLeaves(tree.root);
//        System.out.println(1);
        List<byte[]> memoryHog = new ArrayList<>();
        try {
            while (true) {
                // 创建1GB大小的字节数组（根据系统内存调整大小）
                memoryHog.add(new  byte[1024 * 1024 * 1024]);
                System.out.println("Allocated:  " + (memoryHog.size()  * 1) + "GB");
            }
        } catch (OutOfMemoryError e) {
            System.out.println("Memory  exhausted!");
        }
    }
}
